public class 合并两个有序数组_归并排序 {
    public static int[] tmp;
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m; i < n + m; i++) {
            nums1[i] = nums2[i - m];
        }
        tmp = new int[n + m];
        mergeSort(nums1,0,nums1.length - 1);
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        // [left,mid] [mid + 1,right]
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);
        int cur1 = left;
        int cur2 = mid + 1;
        int cnt = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] < nums[cur2]) {
                tmp[cnt++] = nums[cur1++];
            } else {
                tmp[cnt++] = nums[cur2++];
            }
        }
        while (cur2 <= right) {
            tmp[cnt++] = nums[cur2++];
        }
        while (cur1 <= mid) {
            tmp[cnt++] = nums[cur1++];
        }
        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
        }
    }
}
